A bridge maintains a table (the bridge table) of end stations connected to local area networks having connections to ports of the bridge. When a frame arrives at the bridge, and the frame has a Layer 2 destination address (DA) different from the Layer 2 address of the bridge, the bridge consults its bridge table, determines from the bridge table which port of the bridge to bridge the frame to in order for the frame to reach the destination end station, and transmits the frame to the LAN connected to that port.
In the event that a data frame, or a TEST frame, arrives at a bridge and the destination address of the frame does not appear in the bridge table of the bridge, then the bridge learns the source MAC address from the frame if it is not already present in its bridge table, and then floods the frame to all other ports that are bridged together.
In modern systems, using for example, the DLSw peer to peer protocol, a bridge has another option, in the event that the bridge does not find the end station. By using DLSw implementations the bridge must make a bridging decision for bridging the frame to a distant bridge. The decision is whether to drop the frame, or whether to encapsulate the frame for transmission to a peer router.
A bridge, as described above, bridges frames based upon information in the Layer 2 header of the frame. In contrast, a router routes packets based upon the Layer 3 information carried in the packet. In modern computer systems both a bridge function and a router function are built within one hardware box. The box responds to an incoming frame in order to determine whether or not the frame requires bridging or routing. In some hardware devices, a frame may be bridged by the hardware encapsulating the packet within a header and routing the encapsulated packet over, for example a TCP/IP Layer 3 protocol. A DLSw router is an example of a hardware device which bridges packets by encapsulating them within a header and routing them over a TCP/IP Layer 3 protocol.
One type of router is referred to as a “peer router”, where a plurality of peer routers can reach each other through a network cloud. A DLSw router routing packets within an encapsulation is an example of a peer router. In the event that a peer router determines that a frame which it received must be routed to a corresponding peer router, the router searches for a peer router which can reach the desired destination end station. When a DLSw router receives a frame and determines that the frame must be routed to a peer DLSw router, the receiving DLSw router must determine which peer router can reach the desired destination end station. Another example of peer to peer routing is the Remote Source Route Bridged (RSRB) protocol of Cisco Systems, Inc.
DLSw routing is defined in RFC 1795 of the Internet Engineering Task Force (IETF), all disclosures of which are incorporated herein by reference, and is available at the Web Site www.IETF.org. RSRB routing is described in various documents which can be found at the Web Site www.cisco.com.
When a router provides the service of being a peer router for peer-to-peer encapsulation of a frame through a network between a source peer router to destination peer router, then the source peer router must first determine which peer router can reach the desired destination end station, as in the DLSw example above. Each peer router maintains a table (reachability table) which lists potential destination end stations along with the name of the peer router which can reach the end station. When a frame arrives at a receiving peer router and is addressed to an end station which is not connected to a LAN having a connection to a port of the receiving peer router (as determined from the bridge table and a search of local LANs), the peer router then searches for the desired destination end station in its reachability table.
For sake of clarity we distinguish three different tables maintained by a peer router: first, a bridge table (locally reachable) which the router uses to bridge using Layer 2 frame information from one of its ports to another port, and which is used when is an incoming packet has in its Layer 2 destination address (DA) an address other than the Layer 2 address of the router; second, a reachability table (remotely reachable) which the peer router uses to determine which peer router it should forward an incoming frame to as an extension of its bridging function, such as use of DLSw routing protocol for a frame having a Layer 2 destination address (DA) different from the Layer 2 address of the router; and third, a routing table which the router uses for ordinary Layer 3 routing functions and which is used when an incoming packet has as its Layer 2 destination address (DA) the Layer 2 address of the router. The first two of these tables is often thought of as the “Reachability Table”, and the first part of the table lists the “Locally Reachable” end stations which are reachable through ports of the bridge, while the second part lists the “Remotely Reachable” end stations which are reachable by encapsulating the packet using DLSw protocol, and sending it to a remote DLSw peer. In some designs, the local bridging function, which uses the Locally Reachable portion of the Reachablilty Table, forwards a frame to the DLSw function, if the frame is not locally bridgeable.
If the frame is received by a remote peer from the local peer, the former consults its reachability table, if the destination address is present in its local reachability entries, it directly sends the frame to the corresponding interface; if a peer receives a TEST (explorer) frame it sends it to the remote peer as a CANUREACH frame; the remote peer floods this frame to its locally bridged ports, if the destination MAC address is not present in the remote peer's reachability table.
In the event that the peer router finds the desired destination end station in its reachability table, then the receiving router determines the address of the reachability router from its reachability table. Then the peer router encapsulates the frame and transmits it to the reachability router. Upon receipt of the frame, the reachability router de-encapsulates the frame and transmits it through its port connected to a LAN which has the desired destination end station connected thereto.
For example, in DLSw routing as defined in RFC 1795, the encapsulated frame is routed by the TCP/IP protocol from the receiving DLSw router to the reachability peer DLSw router. The reachability peer DLSw router then de-encapsulates the frame and transmits it through the port which its bridge table tells it is connected to a LAN having the desired destination end station connected thereto.
TEST Frame and CANUREACH Message
In the event that the peer router which received a TEST frame from an end station looks in its reachability table for the desired destination end station and cannot find it listed, the router enters a protocol to find a reachability router. The protocol starts with the receiving router transmitting a CANUREACH message, as defined in RFC 1795, to all of its peer routers.
Upon receipt of the CANUREACH message, each of the peer routers checks its bridge table for the desired destination end station. In the event that a peer router finds the desired destination end station listed in its bridge table, it transmits an ICANREACH message to the receiving router, and upon receipt of the ICANREACH message the receiving router updates its reachability table. The receiving router is now ready to encapsulate the next data frame addressed to the desired destination end station, and send it to the reachability router.
In the alternative event that a peer router receiving the CANUREACH message does not find the desired destination end station in its bridge table, then the peer router floods the TEST frame onto its locally bridged LANs. This test frame looks exactly the same as the TEST frame received by the receiving router which transmitted the CANUREACH message. If the peer router receives a reply from the intended destination end station from one of its locally bridged LANs, the peer router updates its bridge table with the address of the intended destination end station and replies to the receiving peer router with an ICANREACH frame. The receiving router then receives the ICANREACH message and updates its reachability table. Again, the receiving router is now ready to encapsulate the next data frame addressed to the desired destination end station, and send it to the reachability router.
Operational Example
Bridges connect sets of disparate LANs (Ethernet, IEEE 802.5 token ring, FDDI, etc) by Layer 2 bridging. Under everyday engineering practice, there are a number of different types of bridges in everyday use. For example, a source route bridge (SRB) connects token ring and fddi like LANs wherein source bridging is used. Similarly, transparent bridges (TB) connect Ethernet, token ring, fddi, etc. LANs. Also, source route translational bridges (SR/TLB) bridge between transparent and source route bridging domains.
Search messages are used by stations to locate desired receiving stations. These search messages have different names depending upon the technology of the various LANs connected to ports of the router. Neighbor greeting by use of protocols such as Layer 2 LLC TEST and Layer 3 ARP are described by Radia Perlman in her book Interconnections, published by Addison Wesley in 1992, all disclosures of which are incorporated herein by reference, particularly Chapter 2 pages 33-34, and Chapter 3 pages 193-203.
All bridges maintain a table of source addresses (Layer2-MAC) (locally reachable), and this table is populated by a learning process. This table is a Layer 2 level table, and is referred to as the bridge table (locally reachable bridge table), as described hereinabove. When a bridge receives a packet the bridge table is updated with the source MAC and the LAN port on which the packet is received. In the case of SRB, the additional route information field (RIF) information is added to the bridge table entry.
A system of bridged LANs is, however, geographically local, i.e., they are confined to a building or a campus as the bridged system appears as a single LAN. In order to bridge LANs which are geographically separated, Remote Source Route Bridging (RSRB) and Data-Link Switching (DLSw) techniques have been developed.
RSRB deals with source route bridging of two or more remotely connected LANs, and DLSw of RFC 1795 facilitates bridging of remotely connected LANs using TCP/IP to transport packets across IP clouds. DLSw is capable of doing TB, SRB, SR/TLB, etc.
As an example of operation of bridges and DLSw interconnection of geographically separated bridged LANs, consider the following two topologies.
Topology 1
    (station A)—LAN1—-TB bridge—-LAN2—(stations B)Topology 2    (stations A)—LAN1—DLSw router—-IP cloud—DLSw router—-LAN2—(stations B)    Stations A: One or more stations on LAN 1. Stations B: One or more stations on LAN2.In Topology 1 LAN1 and LAN2 are locally connected.
In topology 2 LAN 1, and LAN2 are remotely connected across an IP cloud by DLSw. So LAN1 can be in California and LAN2 in Boston.
Next we examine the situation where A wants to talk to B.
In topology 1, A sends a test frame (an explorer) to station B, the TB bridge receives it, and learns the (MAC) address of A. The TB bridge verifies its bridge table to find out if the address of B (MAC of B) is associated with any of its ports; if it finds the address of B associated with the same port as it received the packet from, it drops the packet since B is also on the same LAN as A. If the TB bridge finds the address of B associated with any other port that is being bridged with the port that is connected to A, it sends that packet out on that port. If the TB bridge does not find address of B at all, it floods an explorer packet onto all other ports (LANs), except for the port on which the packet is received on. Any configurable bridge, such as bridges of present day engineering design, may have many ports connected to different networks, but only a subset of those may be configured as bridged together.
One of these explorer packets will be sent on LAN2 which will reach B, and B replies. As the reply reaches the TB bridge, the TB bridge will learn the address of B (MAC address of B) and update its bridge table for the port connected to LAN2. The destination address in the reply will be the MAC address of A, which the bridge finds in the bridge table as associated with the port connected to LAN1.
The bridge table entries are not permanent, and they are timed out by a timer in the bridge. These entries will be learned again if there is traffic from the stations on different LANs connected to different ports of the bridge. This time out and re-learning mechanism helps to correctly represent the topological development in the whole system of bridges and LANs. For example, station A or B could have moved to some other LAN, or some other port of a bridge, or may have been completely removed from their respective LANs, or, for example, the station itself may have died and be no longer functional.
Now, in topology 2, the mechanism for A to talk to B is essentially the same as in topology 1, with the additional function of the DLSw router flooding the explorer packets onto all of its DLSw peer routers. That is, in the bridging function, DLSw router1 floods the explorer packet it received to any other ports that are bridged to the input port of the explorer, with the additional function that the DLSw module also floods the explorer packet onto all of the DLSw links to peer DLSw routers. Also, to A all of the DLSw operations appear in Layer 2, even though the DLSw router uses Layer 3 to bridge packets using TCP/IP over an Internet cloud.
The DLSw module is, under standard engineering practice, a software routine which supplies the DLSw functionality. The DLSw module maintains a table of its own, called the “reachability cache”, by learning the MAC address of A as locally reachable. The DLSw reachability cache can be viewed as two caches, one locally reachable such as given by the bridge table, the other remotely reachable such as is given by the “reachability table” mentioned hereinabove. In some engineering design, the bridge software module maintains the bridge table, while the DLSw software module maintains a similar “locally reachable cache”, even these two tables are substantially the same. In engineering designs where two separate tables are maintained, there must be a synchronization mechanism implemented so that updates in one of the tables is immediately transferred to the other table. In alternative engineering designs, the Layer 2 bridge software module and the Layer 3 DLSw software module share the same bridge table. The DLSw module then verifies its reachability cache table entries for the MAC address of B. If the MAC address of B is found as locally reachable, the DLSw router1 drops the explorer, since the bridging function (in this case TB) takes care of dealing with that explorer. If the DLSw router1 finds the MAC address of B as remotely reachable through its peer DLSw router2, then DLSw router1 sends a response back to the originator A as if B has responded. Else, it transports the explorer to its peer (CANUREACH message), DLSw router2, over the TCP/IP connection that the two peers have established.
DLSw router2, upon receiving the explorer, updates its Leachability cache with the MAC address of A as remotely reachable through its peer DLSw router1. DLSw router2 then verifies its reachability cache for the MAC address of B. If DLSw router 2 finds the MAC address of B, it sends a response back to DLSw router1 that it can reach B (ICANREACH message). DLSw router1, now, updates its reachability cache with B's MAC address as remotely reachable through its peer DLSw router2, and in turn replies to A as if B has responded to A's explorer.
However, if DLSw router2 does not find B's MAC address in its reachability cache, it sends explorers to all the ports (LANS, in effect) the DLSw function is being bridged together with. An explorer goes onto LAN2, reaches B, and B replies. DLSw router2 now updates its reachability cache (locally reachable cache, or bridge table) with B's MAC address as locally reachable, and sends an ICANREACH message to its peer DLSw router1. DLSw routerr then updates its reachability cache (remotely reachable), and responds to A's explorer for B by replying to A.
Excessive TEST Frame Flooding
It is important to note that each of these DLSw routers may have multiple local LANs bridged together, and may be peering with multiple DLSw routers. So an explorer sent by A could potentially be flooded onto multiple LANs, all of which are connected to DLSw router1's peers, in addition to flooding the IP networks (often low bandwidth serial lines) that DLSw router1 is peering across. This situation becomes progressively worse when many stations on LAN 1 try to talk to different stations, including those stations on LAN2, and on other LANs.
Typically, only a few (perhaps only one) peer routers will be connected to a LAN having the desired destination end station connected thereto. There may be several hundred peer routers which receive the CANUREACH message, and each of them will transmit their local LAN search messages through each port. The result is that a large amount of network bandwidth is consumed by the various search messages.
It is desirable to operate a peer-to-peer routing protocol while consuming a minimum of network bandwidth from transmission of search messages searching for end stations which do not appear in a bridge table of a router.